"""
左偏树静态结构

remove: 删除[任意堆的]任意节点
"""

MAXN = 100001
nums = [0] * MAXN
up = [0] * MAXN  # 当前节点的父亲节点
left = [0] * MAXN
right = [0] * MAXN
dist = [0] * MAXN
father = [0] * MAXN


def init(n):
    dist[0] = -1
    for i in range(1, n + 1):
        up[i] = left[i] = right[i] = dist[i] = 0
        father[i] = i


# 并查集的find 找头
def find(x):
    if x != father[x]:
        father[x] = find(father[x])
    return father[x]


# 合并两个堆
def merge(x, y):
    if x == 0 or y == 0:
        return x + y
    if nums[x] > nums[y] or (nums[x] == nums[y] and x > y):
        x, y = y, x
    right[x] = merge(right[x], y)
    up[right[x]] = x  # 在当前树右树上合并后，设置后右树的父节点

    if dist[left[x]] < dist[right[x]]:
        left[x], right[x] = right[x], left[x]

    dist[x] = dist[right[x]] + 1
    father[left[x]] = father[right[x]] = x
    return x


# 删除当前堆的根节点
def pop(x):
    father[left[x]] = left[x]
    father[right[x]] = right[x]

    # 清空我的信息, 不进行真实删除
    # 但是并查集的信息要维护：可能之前有节点直接find，路径压缩，直连的我，所以要继续维护这个并查集的信息
    s = merge(left[x], right[x])
    father[x] = s
    up[s] = up[x]
    left[x] = right[x] = dist[x] = 0
    return father[x]    # 当前堆的新头


# 删除任意堆的任意节点，并合并左右子树，最终返回合并后的堆的头节点
def remove(x):
    root = find(x)
    if root == x:
        return pop(x)
    father[left[x]] = left[x]
    father[right[x]] = right[x]

    s = merge(left[x], right[x])  # same as pop
    f = up[x]  # 当前节点的父节点
    father[x] = s  # same as pop
    up[s] = f  # 维护好新合并树的头节点
    # 调整好树的结构
    father[s] = root
    if left[f] == x:
        left[f] = s
    else:
        right[f] = s

    # 维护好左偏树性质: 一路向上，可能的修正dist，以及可能的需要左右子树交换
    cur, f = s, f
    while dist[f] > dist[cur] + 1:
        dist[f] = dist[cur] + 1
        if dist[left[f]] < dist[right[f]]:
            left[f], right[f] = right[f], left[f]
        cur = f
        f = up[cur]

    # 清空删除节点的信息
    up[x] = left[x] = right[x] = dist[x] = 0
    return father[s]    # 当前堆的根
